package com.qch.leecode.cyc2018.algorithm.a2_sort;

import com.qch.leecode.cyc2018.util_comom.Common;

import java.util.*;

/**
 * 算法思想：排序(桶排序)：347. 前 K 个高频元素
 * https://leetcode.cn/problems/top-k-frequent-elements/
 * @Author qch
 * @Date 2022/11/16
 *自己解题需注意：
 * 1.定义桶的个数的时，桶下标是元素出现次数，因此不会超过原数组长度
 * 2.在找寻topk时因为桶下表已经时排好序的，因此找前k多倒叙就可以
 *
 * 解题思想：桶排序(桶思想很重要)--均匀分布
 * 设计区间范围的桶例如5个，第一个放0-10，第二个11-20
 * 然后对每个桶里的数据进行排序，然后再将所有桶合并
 *
 * 题目：给你一个整数数组 nums 和一个整数 k ，
 * 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
*/
public class L2_TopKFrequent347 {
    public static void main(String[] args) {

        int[] numbers={2,2,1,3,3,3};
        int target=2;
        int[] kthLargest = topKFrequent(numbers,2);
        Common.toString(kthLargest);

    }


    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer>map=new HashMap<>();
        for (int num : nums) {
            Integer integer = map.get(num);
            if(map.get(num)==null)
            {
                map.put(num,1);
            }else {
                map.put(num,integer+1);
            }
        }
        //桶的个数最大不超过原数组长度，因为fluency是下标，最大不超过最大不超过原数组长度
        List[] bukets=new ArrayList[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer fluency = entry.getValue();
            Integer key = entry.getKey();
            if (bukets[fluency]==null) {
                bukets[fluency] = new ArrayList() {
                };
            }
            bukets[fluency].add(key);
        }
        //因为bukket的i下标就是有序的，是数字的count计数，所以倒序遍历即可
        List<Integer>topKlist=new ArrayList<>();
        for (int i = bukets.length - 1; i >= 0&&topKlist.size()<=k; i--) {
            if (bukets[i]!=null) {
                if (bukets[i].size() <= k - topKlist.size()) {
                    topKlist.addAll(bukets[i]);
                } else {
                    //可以替换成一行代码：topK.addAll(buckets[i].subList(0, k - topK.size()));
                    for (int j = 0; j < k - topKlist.size(); j++) {
                        topKlist.add((Integer) bukets[i].get(j));
                    }
                }
            }
        }
        int[] topkArray=new int[topKlist.size()];
        for (int i = 0; i < topKlist.size(); i++) {
            topkArray[i]=topKlist.get(i);
        }
        return topkArray;
    }
}
